“Optimum” Strategies for Information Security

Mike O'Leary

Towson University

Collaborators

Andrew Engel, Towson University

Ferenc Szidarovszky, University of Arizona

Michael Jones, Montclair State University

Shiva Azadegan, Towson University

Question

What is the optimal method to defend a computer network from attack?

What is optimal?

The Posture Question

There are many technical things that can be done to improve security.

Each of these comes at a cost.

“Optimal” then means to balance cost versus risk.

This is the Posture Question:
What is the right level of security for a particular network or enterprise?

The Active Defense Question

Suppose that your firewall logs or intrusion detection system show some unusual activity. Are you under attack?

Key information may be false, missing, or misleading.

This is the active defense question:
What is the right way to respond to a perceived attack?

Game Theory

In each case, we are trying to make “optimal” decisions under uncertainty.

Mathematicians call the study of these questions Game Theory.

Game Theory

O. Morgenstern & J. von Neumann, Theory of Games and Economic Behavior, 1944.

J. Nash, Equilibrium Points in n-Player Games, 1950.

Applications to Computer Security

T. Alpcan & T. Basar, A Game Theoretic Approach to Decision and Analysis in Network Intrusion Detection, Proceedings of the 42nd IEEE Conference on Decision and Control, 2003.

S.N. Hamilton, W.L. Miller, A. Ott & O.S. Saydjari, The Role of Game Theory in Information Warfare, The Fourth Information Survivability Workshop, 2002.

M. Kodialam & T.V. Laskhman, Detecting Network Intrusions via Sampling: A Game Theoretic approach, Proceedings of the 22nd Annual Joint Conference of the IEEE Computer and Communication Societies, 2003.

The Model

The attacker has a finite number of attacks

is the probability that the attack will succeed against an average target.

is the probability that the attack will be detected by an average target.

To be useful, this model will need reasonable values for these parameters. These are comparable to the severity metric from the U.S. Computer Emergency Readiness Team (www.kb.cert.org/vuls/bymetric)

The Model

We assume that the defender has a finite number of defenses

is the probability that an average attack will succeed against this target

is the probability that an average attack will be detected against this target.

The Model

Let be the probability of success for an attack of strength against a target with strength .

Let be the strength of the average attack, and be the strength of the average defense.

Then and so that .

The Model

We use the simplest model, which is piecewise linear:

Even if this model is not valid globally, it will be a good approximation near the average

The Model

Suppose that the attacker has possible attacks for
while the defender has possible defenses for

A strategy for the attacker is a choice of , while a strategy for the defender is a choice of

A mixed strategy is a probability distribution on the set of strategies

The Model

Let be a mixed strategy for the attacker, so that and .

Similarly, let be a mixed strategy for the defender.

The Model

Let be the matrix of success probabilities, so that the expected success probability is
.

Similarly, let be the matrix of detection probabilities so that the expected detection probability is
.

The Payoff

The attacker has two goals- to succeed and to remain undetected. To account for this, the attacker tries to maximize his payoff function
Here we used the normalization
and the definition

The Payoff

The defender has three goals- to defeat the attacker, to detect the attacker, and to do so at minimal cost.

For each defender strategy let be the associated cost, and let

The Payoff

Assign the weights

to attacker success

to attacker detection

to the cost

The defenders payoff function is then

Equilibrium Solutions

A Nash Equilibrium is a pair of strategies so that
for all
and
for all

Equilibrium Solutions

A game in this form is called a bimatrix game.

It is known that every bimatrix game has an equilibrium point.

The Quadratic Program

Maximize

Such that

Equilibrium Solutions

Recall that while
.

The attacker payoff is

Equilibrium Solutions

Equilibrium occurs when
where is chosen so that
is as large as possible.

Similarly, equilibrium for the defender occurs when
where is chosen so that
is as large as possible.

Consequences

Equilibrium solutions are pure strategies.

Equilibrium solutions depend only on your parameters; the strength of the opponent is irrelevant.

Caveats

The model is very abstract.

The calculation of equilibria depends strongly on the precise form of the probability function

This is probably not a reasonable assumption for interactions that are far from average- e.g. highly secure networks or highly skilled attackers.

Next Steps

Success of an attack is not truly probabilistic; rather it is determinate, but unknown to either party.

Need to look at games with incomplete information

Real situations are interactive, and take place over time.

Need to look at iterated games.

Questions?

2004-10-13T20:29:00